//
// Description: 446. 等差数列划分 II - 子序列
// Created by Loading on 2021/8/11.
//

#include <bits/stdc++.h>

using namespace std;

int numberOfArithmeticSlices(vector<int> &nums) {
    // dp[i][d] 表示以 nums[i] 元素结尾的，公差为 d 的等差数列的个数
    /* dp 数组包含长度为 2 的等差数列 */
    vector<unordered_map<long long, int>> dp(nums.size());

    int res = 0;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            // 计算当前项与此项之前的所有元素的公差
            long long d = nums[i] - nums[j] * 1LL;
            // 累加结果，注意累加的是 dp[j][d]，加上此项，数列长度至少为 3
            res += dp[j][d];
            // 更新 dp 数组
            dp[i][d] += dp[j][d] + 1;
        }
    }

    return res;
}

int main() {
    vector<int> nums = {2, 4, 6, 8, 10};
    int res = numberOfArithmeticSlices(nums);
    cout << res << endl;
}